package com.tulingxueyuan.array;

import java.util.Arrays;

/**
 * 合并两个有序数组
 * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，
 * 分别表示 nums1 和 nums2 中的元素数目。
 * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
 * 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，
 * 后 n 个元素为 0 ，应忽略。nums2 的长度为 n
 */
public class MergeSorteArray_88 {
    //方法一 直接利用数组排序方法 数组合并后在一起排序, 时间复杂度为:o(m+n)log(m+n)), 空间复杂度为:o(log(m+n))
//    public void merge(int[] nums1,int m,int n,int[] nums2){
//        for (int i = 0; i <n ; i++) {
//            nums1[m+i] = nums2[i];
//        }
//        Arrays.sort(nums1);
//    }

    //方法二 双指针 临时数组
//    public void merge(int[] nums1,int m,int[] nums2,int n){
//        int k = m+n;
//        int[] temp = new int[k];
//        for (int index = 0,nums1Index = 0,nums2Index = 0; index < k; index++) {
//            if(nums1Index >= m){ //nums1数组里的元素取完了
//                temp[index] = nums2[nums2Index++];
//            }else if(nums2Index >= n){ //nums1数组里的元素取完了
//                temp[index] = nums1[nums1Index++];
//            }else if(nums1[nums1Index] < nums2[nums2Index]){ //nums1数组里的元素小于nums2数组里的元素
//                temp[index] = nums1[nums1Index++]; //取nums1数组里的值
//            }else{
//                temp[index] = nums2[nums2Index++];
//            }
//        }
//
//        for(int i = 0;i < k;i++){
//            nums1[i] = temp[i];
//        }
//    }

    //方法三 双指针 从后往前遍历
    public void merge(int[] nums1,int m,int[] nums2,int n){
        int k = m+n;
        for(int index = k-1,nums1Index = m-1,nums2Index = n-1;index >= 0;index--){
            if(nums1Index < 0){ //nums1已经取完了,完全取nums2的值
                nums1[index] = nums2[nums2Index--];
            }else if(nums2Index < 0){ //nums2已经取完了,完全取nums1的值即可
                break;
            }else if(nums1[nums1Index] > nums2[nums2Index]){ //nums1的元素值大于nums2,取nums1的值
                nums1[index] = nums1[nums1Index--];
            }else{ //nums2的元素值大于等于nums1,取nums2的值
                nums1[index] = nums2[nums2Index--];
            }
        }
    }


}
